package com.apkcore.bl;

/**
 * https://leetcode-cn.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/
 */

import java.util.ArrayList;
import java.util.List;

public class _1239串联字符串的最大长度 {
    //输入：arr = ["un","iq","ue"]
    //输出：4
    //解释：所有可能的串联组合是 "","un","iq","ue","uniq" 和 "ique"，最大长度为 4。
    public static void main(String[] args) {
        List<String> arr = new ArrayList<>();
        arr.add("abc");
        arr.add("dabcsf");
        System.out.println(new _1239串联字符串的最大长度().maxLength(arr));
    }

    int ans;

    /**
     * 看到题目想到的是dfs深度遍历，那么就需要去重
     * 这里用到一个技巧，使用二进制来去重，0号位表示a，以此类推
     * 1表示这一位已经有重复计算了，那么回溯时去掉
     */
    public int maxLength(List<String> arr) {
        if (arr == null || arr.size() == 0) {
            return 0;
        }
        List<Integer> masks = new ArrayList<>();
        for (String str : arr) {
            int mask = 0;
            char[] chars = str.toCharArray();
            for (char c : chars) {
                int ch = c - 'a';
                if ((1 & (mask >> ch)) != 0) {
                    mask = 0;
                    break;
                }
                mask = mask | 1 << ch;
            }
            if (mask > 0) {
                masks.add(mask);
            }
        }
//        for (Integer mask : masks) {
//            System.out.println(Integer.toBinaryString(mask));
//        }
//        System.out.println("------------------------------");
        cacule(masks, 0, 0);
        return ans;
    }

    private void cacule(List<Integer> masks, int pos, int mask) {
        if (pos == masks.size()) {
            // 到了最后一个，求最后一个的长度与ans求出最大值
            ans = Math.max(ans, Integer.bitCount(mask));
            return;
        }
        if ((mask & masks.get(pos)) == 0) {
            cacule(masks, pos + 1, mask | masks.get(pos));
        }
        cacule(masks, pos + 1, mask);
    }

}
